# -*-coding:utf-8-*-
__author__ = 'wss'

from graph import *
from a_star_search import *
from draw_graph import *
import pandas as pd
import time
import math
import multiprocessing
import matplotlib.pyplot as plt

def kruskal_link(graph):  # 适合简单图
    result = []
    if (graph.get_nodenum() <= 0) or (graph.get_edgenum() < graph.get_nodenum() -1):
        return result
    node_list, edge_list = graph.get_weight_list()
    edge_list.sort(key=lambda x:x[2])  # 对边按权重排序
    group = [[i] for i in range(graph.get_nodenum())]
    for edge in edge_list:
        for i in range(len(group)):  # 找到边的开始结点和结束结点所在树
            if edge[0] in group[i]:
                m = i  # 开始结点
            if edge[1] in group[i]:
                n = i  # 结束结点
        if m != n:
            result.append(edge)
            group[m] = group[m] + group[n]  # 将新边的两个结点都放到开始结点所属树中，将结束结点所属树清空
            group[n] = []
    return node_list, result

def prim_link(graph):  # 适合稠密图
    result = []
    if (graph.get_nodenum() <= 0) or (graph.get_edgenum() < graph.get_nodenum() -1):
        return result
    node_list, weight_matrix = graph.get_weight_matrix()
    selected_node = [0]
    candidate_node = [i for i in range(1,graph.get_nodenum())]

    while len(candidate_node) > 0:
        begin, end, minweight = 0, 0, MAX_PATH
        for i in selected_node:
            for j in candidate_node:
                if weight_matrix[i][j] < minweight:
                    minweight = weight_matrix[i][j]
                    begin = i
                    end = j
        result.append([begin, end, minweight])
        selected_node.append(end)
        candidate_node.remove(end)
    return node_list, result


# def isPointIntersectsSegment(p, s, e):
#     a = (s[0] - p[0], s[1] - p[1])
#     b = (e[0] - p[0], e[1] - p[1])
#     a_cross_b = a[0] * b[1] - b[0] * a[1]
#     x_flag = min([s[0], e[0]]) <= p[0] <= max([s[0], e[0]])
#     y_flag = (min((s[1], e[1])) <= p[0] <= max((s[1], e[1])))
#     if (a_cross_b == 0) and x_flag and y_flag:
#         return True
#     return False

def func(gridgraph,idx_i,idx_j):
    # print idx_i,idx_j
    result = {}
    came_from, cost_so_far = a_star_search(gridgraph, idx_i, idx_j)
    result[(idx_i,idx_j)] = cost_so_far
    return result  # cost_so_far

def draw_path_graph(graph_result, node_list, came_from_list,width,height):

    path = []
    for idx_p in graph_result:
        start = node_list[idx_p[0]]
        goal = node_list[idx_p[1]]
        if (start,goal) in came_from_list.keys():
            if len(came_from_list[(start, goal)])>0:
                path = path + reconstruct_path(came_from_list[(start, goal)], start=start, goal=goal)
        else:
            if len(came_from_list[(goal, start)]) > 0:
                path = path + reconstruct_path(came_from_list[(goal, start)], start=goal, goal=start)

    # draw_grid(diagram5, width=1, path=list(set(path)),start=node_list_2)

    path_arr = np.zeros((width,height))
    for idx in path:  # 路径点位
        path_arr[idx[0],idx[1]] = 5
    for idx in node_list:  # 风机点位
        path_arr[idx[0],idx[1]] = -5
    path_df = pd.DataFrame(path_arr)
    x_list = []
    for idx in range(width):
        if idx%50==0:
            x_list.append(idx+1)
        else:
            x_list.append('')
    y_list = []
    for idx in range(width):
        if idx % 50 == 0:
            y_list.append(idx + 1)
        else:
            y_list.append('')
    plt.figure()
    data = path_df
    plt.pcolor(data, cmap=plt.cm.PRGn_r, vmin=-5, vmax=5)  # 设置colorbar的范围 , edgecolors='white'
    plt.xticks(np.arange(width) + 0.5, x_list)
    plt.yticks(np.arange(height) + 0.5, y_list, rotation=30)
    plt.xlim([0, width])
    plt.ylim([0, height])
    plt.xlabel('width')
    plt.ylabel('height')
    # plt.colorbar()
    plt.title('test')
    for idx in node_list:
        plt.text(idx[1]+0.3,idx[0],str((idx[1],idx[0])))
    plt.show()

def make_graph(diagram, graph, node_list, dis_limit):
    """
    :param diagram:网格图
    :param graph: 网络图
    :param node_list: 风机点位
    :param dis_limit: 限制超出该距离不使用A*算法计算
    :return: 路径列表
    """
    MAX_WEIGTH = 300
    came_from_list = {}
    for idx_i in node_list:
        for idx_j in node_list:
            if (idx_i != idx_j):
                if graph.weights.get((idx_j, idx_i)):
                    graph.edges.setdefault(idx_i, []).append(idx_j)
                    graph.weights[(idx_i, idx_j)] = graph.weights[(idx_j, idx_i)]
                else:
                    if (heuristic(idx_i, idx_j) < dis_limit):
                        came_from, cost_so_far = a_star_search(diagram, idx_i, idx_j)
                        came_from_list[(idx_i, idx_j)] = came_from
                        graph.edges.setdefault(idx_i, []).append(idx_j)
                        graph.weights[(idx_i, idx_j)] = cost_so_far[idx_j]
                    else:
                        came_from_list[(idx_i, idx_j)] = []
                        graph.edges.setdefault(idx_i, []).append(idx_j)
                        graph.weights[(idx_i, idx_j)] = MAX_WEIGTH
    return came_from_list

def make_diagram(width,height,walls):
    """
    :param width:
    :param height:
    :param walls: 障碍物点
    :return: 赋权网格图
    """
    diagram = GridWithWeights_new(width, height)
    diagram.walls = walls
    for idx_x in range(width):
        for idx_y in range(height):
            from_node = (idx_x, idx_y)
            if from_node not in diagram.walls:  # 出发结点不能是障碍结点
                from_node_neighbors_straight = diagram.neighbors_straight(from_node)
                if len(from_node_neighbors_straight) > 0:
                    for neighbor in from_node_neighbors_straight:
                        diagram.weights[(from_node, neighbor)] = 1
                from_node_neighbors_inclined = diagram.neighbors_inclined(from_node)
                if len(from_node_neighbors_inclined) > 0:
                    for neighbor in from_node_neighbors_inclined:
                        diagram.weights[(from_node, neighbor)] = math.sqrt(2)
    return diagram

def main():
    # 定义10*10网格图，同时定义各方向权重

    random.seed(1)
    width = 300
    height = 300
    t_num = 50
    # 随机生成100个机位点
    t_list = set()
    while len(t_list)<t_num:
        n = random.randrange(width*height)
        t_list.add((n/width,n%width))
    print t_list
    start_t = time.time()
    diagram5 = make_diagram(width,height,[])  # 创建网格图
    end_t = time.time()
    print end_t-start_t
    # 测试100台风机寻找最短路径时间:共100*（100-1）/2条边
    start_t = time.time()
    node_list = list(t_list)
    grapht = Graph()  # 先根据网格距离排除不必要的距离计算
    # # 尝试多进程
    # pool = multiprocessing.Pool(4)
    # tmp = []
    # for idx_i,val_i in enumerate(node_list):
    #     for idx_j,val_j in enumerate(node_list):
    #         if idx_i > idx_j:
    #             tmp.append(pool.apply_async(func, args=(diagram5,val_i, val_j)))  # [(val_i, val_j)] =
    # pool.close()
    # pool.join()
    # cost_so_far = {}
    # for t in tmp:
    #     print t.get()
    #     cost_so_far[t.get().keys()[0]] = t.get().get(t.get().keys()[0])
    # end_t = time.time()
    # print end_t - start_t
    #
    # for idx_i,val_i in enumerate(node_list):
    #     for idx_j,val_j in enumerate(node_list):
    #         grapht.edges.setdefault(val_i, []).append(val_j)
    #         if idx_i > idx_j:
    #             # for i in cost_so_far[(val_i,val_j)]:
    #             grapht.weights[(val_i, val_j)] = cost_so_far[(val_i,val_j)][val_j]
    #         elif idx_i< idx_j:
    #             # for i in cost_so_far[(val_j,val_i)]:
    #             grapht.weights[(val_i, val_j)] = cost_so_far[(val_j,val_i)][val_i]
    came_from_list = make_graph(diagram5,grapht,node_list,200)  # 创建全连接网络图
    print 'kruskal path'
    node_list_1, result_1 = kruskal_link(grapht)
    print result_1
    end_t = time.time()
    print end_t - start_t
    print 'prim path'
    node_list_2, result_2 = prim_link(grapht)
    print result_2
    end_t = time.time()
    print end_t - start_t

    # 绘制图
    # draw_grid(diagram5, width=3, number=cost_so_far, start=start, goal=goal)
    # print ''
    # draw_grid(diagram5, width=3, path=reconstruct_path(came_from, start=start, goal=goal))
    # print 'cost:%d' % cost_so_far.get(goal)

    draw_path_graph(result_2, node_list_2, came_from_list, width, height)

    print 'finished'



    # start, goal = (1, 4), (170, 180)
    # came_from, cost_so_far = a_star_search(diagram5, start, goal)
    # end_t = time.time()
    # print end_t - start_t
    # draw_grid(diagram5, width=3, point_to=came_from, start=start, goal=goal)
    # print ''
    # draw_grid(diagram5, width=3, number=cost_so_far, start=start, goal=goal)
    # print ''
    # draw_grid(diagram5, width=3, path=reconstruct_path(came_from, start=start, goal=goal))
    # print 'cost:%d' % cost_so_far.get(goal)
    #
    # # flag = isPointIntersectsSegment((2,4),(2,6),(2,1))
    # # 测试点是否在多边形内
    # bound_list = [(2,1),(8,1),(8,6),(5,4),(2,6)]
    # id_list = [(7,5)]
    # for id in id_list:
    #     flag = diagram5.in_defbounds(id,bound_list)
    #     print flag
    # print '带边界的最短路径搜索：'
    # diagram5.set_wall(bound_list)  # 有了边界之后的最短路径搜索
    # start, goal = (2, 1), (8, 6)
    # came_from, cost_so_far = a_star_search(diagram5, start, goal)
    # draw_grid(diagram5, width=3, point_to=came_from, start=start, goal=goal)
    # print ''
    # draw_grid(diagram5, width=3, number=cost_so_far, start=start, goal=goal)
    # print ''
    # draw_grid(diagram5, width=3, path=reconstruct_path(came_from, start=start, goal=goal))
    # print 'cost:%d' % cost_so_far.get(goal)
    #
    #
    # # 对多个点相互求距离
    # node_list = [(1, 4), (7, 8), (6, 2), (3, 9), (4,2)]  # 风机点位
    # grapht = Graph()
    # for idx_i in node_list:
    #     for idx_j in node_list:
    #         if idx_i != idx_j:
    #             came_from, cost_so_far = a_star_search(diagram5, idx_i, idx_j)
    #             grapht.edges.setdefault(idx_i, []).append(idx_j)
    #             grapht.weights[(idx_i, idx_j)] = cost_so_far[idx_j]
    # node_list, weight_matrix = grapht.get_weight_matrix()
    # print 'nodenum:%d'%grapht.get_nodenum()
    # print 'edgenum:%d'%grapht.get_edgenum()
    # node_list, weight_list = grapht.get_weight_list()
    # print 'weight_list'
    # print weight_list
    # print 'kruskal path'
    # node_list_1, result_1 = kruskal_link(grapht)
    # print result_1
    # print 'kruskal path'
    # node_list_2, result_2 = prim_link(grapht)
    # print result_2
    # print ''

if __name__=='__main__':
    main()